1. Field of the Invention
The present invention relates to an arithmetic coding apparatus and image processing apparatus.
2. Description of the Related Art
An arithmetic coding system that predicts a coding symbol based on states of already coded pixels and carries out arithmetic coding on the prediction result based on a probability estimate of the coding symbol determined for each state is known to have the most excellent characteristic in terms of compressibility.
A QM-coder, a coder adopted by JBIG (ITU Recommendation T.82), is a typical example of an apparatus for carrying out arithmetic coding.
A general configuration and operation of the QM-coder, which is an arithmetic coder for binary images, will be explained below.
As shown in FIG. 18, the QM-coder comprises context generation section 200, context table (context memory) 210, probability estimator 220 and arithmetic coder 230.
Context generation section 200 detects 1024 states created by 10 pixels surrounding to a coding pixel. FIG. 20 shows an example of a template.
xe2x80x9c?xe2x80x9d in the figure is the coding pixel and the 10 pixels marked xe2x80x9cxxe2x80x9d are reference pixels. When coding of one pixel is completed, the template is shifted by one rightward as shown with dotted line in FIG. 20 and coding of the next pixel is performed.
Each of 1024 states determined by the values of 10 pixels is called xe2x80x9ccontextxe2x80x9d (hereinafter expressed with xe2x80x9cSxe2x80x9d). A predicted value of a more probable symbol MPS(s) (that is, if MPS of the coding pixel is predicted as xe2x80x9c1xe2x80x9d by the context s, MPS(s)=1) and a state number of the probability estimator are read from context memory for each context and output to probability estimator 220.
Probability estimator 220 outputs interval width of a less probable symbol Qe(s) to arithmetic coder 230 based on this information. Here, xe2x80x9cQexe2x80x9d is a probability that LPS will occur and the present specification sometimes refers to Qe as a xe2x80x9csymbol occurrence probabilityxe2x80x9d or simply as a xe2x80x9cprobability estimatexe2x80x9d.
Furthermore, interval width of a less probable symbol Qe(s) means the width corresponding to the probability of occurrence of LPS which is calculated by multiplying the probability of occurrence of LPS by the width of an augend. The augend refers to the overall width of a number line shown in FIG. 19.
Arithmetic coder 230 performs arithmetic coding calculations based on the coding symbol, predicted value of MPS(S), and interval width Qs(s), and outputs code stream.
As shown in FIG. 19, arithmetic coding divides a number line of initial value 0 to 1 into two sub-intervals of a more probable symbol (MPS) and a less probable symbol (LPS). A series of coding symbols is associated with a point (a coding point) some where within each sub-interval. For the simplicity, the QM-coder uses the convention that the coding point is located at the bottom of the sub-interval.
When a coding symbol matches a predicted value, an MPS width is selected for coding of the symbol and an LPS width is selected otherwise.
As described above, a coding point is provided in this sub-interval and a binary fraction of the point denotes an arithmetic code stream.
When the interval width falls short of a predetermined value, an arithmetic coding calculation repeats the doubling operation until the interval width exceeds a predetermined value (more specifically xc2xd of the initial value) to maintain the accuracy of decimal points. This processing is called xe2x80x9crenormalizationxe2x80x9d.
Renormalization is also carried out when LPS is coded. That is, when an LPS width is selected as a result of estimation failure, the LPS width is always smaller than xc2xd of the initial value and therefore renormalization is performed every time.
When renormalization is performed, the MPS value and state number (ST) in context table 210 in FIG. 18 are updated. The state number is updated when the xe2x80x9cnext state numberxe2x80x9d written in probability estimation section 220 is overwritten in context table 210. In FIG. 18, this overwrite is indicated by an arrow RX.
With this update of the context table 210, even if the next context is also the same as the previous context (that is, even if the template in FIG. 20 is shifted by one rightward, the positions of 1 and 0 of the reference pixels are the same as the previous positions), the value of Qe(S) that occurs is different.
In this way, a Qe (S) value suitable for a probability distribution of the information source is selected. That is, the coding parameter Qe (s) is more adapted to the target image.
Here, the coding target is not limited to binary data. Multi-valued data such as continuous-tone image can also be coded using the QM-coder. However, it is necessary to use a context model which matches the coding target.
For example, a discrete cosine transform coefficient (DCT coefficient) includes a DC component and AC component. The both components have different natures of signal. Therefore, it is important to construct a context model suited to these natures in improving the coding efficiency.
In the current technology, different contexts are created for the DC component and AC component.
The conventional arithmetic coding processing has the following problems.
(Problem 1)
Originally, arithmetic coding is excellent in compressibility, but since it is necessary to repeat generation of a context, estimation of symbol occurrence probability and arithmetic code calculation symbol by symbol, arithmetic coding has a disadvantage that it requires a long processing time. A reduction of the processing speed is quite a big problem in such a field as a digital copier that requires high image quality and high speed processing.
Furthermore, when arithmetic coding is pipelined, if renormalization occurs at some midpoint, disturbance occurs with the pipeline resulting in an increase of useless wait time. The processing efficiency may reduce in this way. Especially, renormalization occurs with considerable frequency and pipeline disturbance is likely to occur in image patterns whose context has continuity. The same problem may also occur in the case of decoding.
Therefore, even if arithmetic coding is pipelined, the accuracy cannot be said to be high and speeding up of arithmetic coding/decoding is not expected much.
(Problem 2)
It is desirable to carry out high accuracy pipeline processing in the case of not only coding of binary data but also coding or decoding of multi-valued data (e.g., numerical data such as orthogonal transform coefficient, etc. obtained by JPEG compression).
However, high-speed arithmetic coding or decoding of numerical values such as orthogonal transform coefficients involves the following problems.
That is, making pipeline processing effectively requires data necessary for the next pipeline stage to be supplied continuously at a constant rate.
For example, performing high-speed decoding requires context indices to be supplied simultaneously to a plurality of symbols which are likely to be reconstructed. A set of these context indices will be called xe2x80x9ccontext index vectorxe2x80x9d.
It is actually difficult to supply context data of such a vector format at a constant rate. As described above, an orthogonal transform coefficient includes a DC component and AC component. Since the DC component and AC component have statistically different natures, the current technology provides different contexts for the respective components.
It is difficult to supply different contexts consecutively. Thus, when DC components and AC components are mixed in a plurality of symbols to be coded, it is difficult to supply a context index vector at a constant rate.
Therefore, high-speed arithmetic coding of multi-valued data is more difficult than in the case of binary data.
(Problem 3)
It would be convenient if it is possible to divide an input image into blocks of a predetermined size, apply arithmetic coding block by block independently and freely perform decoding in block units.
However, since an arithmetic code is a variable-length code, the code length of a code corresponding to one block is not constant. Therefore, when arithmetic-coded image data is reconstructed and the orientation of the image is changed for only some blocks, it is difficult to find pixel data at the start of the target block.
In view of these situations, it is an object of the present invention to implement ultra-high-speed and high compressibility arithmetic coding or decoding irrespective of binary data or multi-valued data, and coordinate the amount of arithmetic coding per block to a fixed value and simplify the subsequent processing.
(1) When a coding parameter needs to be updated, the arithmetic coding apparatus of the present invention outputs a probability estimate (future probability estimate) which is expected to be output after the parameter is updated in parallel with the current estimated value (probability estimate output through normal processing). Then, when a predetermined situation occurs (for example, a parameter needs to be updated and contexts are generated consecutively and therefore contention occurs between writes and reads of RAM), a future estimated value rather than the current estimated value is supplied to the coder. This eliminates the need to wait for coding while updating parameters by carrying forward the loop, thus preventing disturbance in the pipeline.
(2) The present invention discards the conventional fixed concept that attaches absolute importance to compressibility and introduces a new concept that attaches primary importance to the processing speed. Based on this concept, the present invention positively use contexts common to both the DC component and AC component.
Then, the present invention makes it possible to generate context indices using a state transition table for both coding and decoding.
This makes it easier to generate a context index vector during decoding and implement a coder or decoder suitable for pipeline processing. Since the coding context is simplified, the compression performance deteriorates more or less. However, the present invention analyzes information of an input image accurately through image area decision or layering processing, etc. and performs high precision compression, causing no problem in this respect.
Furthermore, it is often the case that higher priority is given to the processing speed than the image quality, causing no practical problem.
The present invention can perform arithmetic coding or arithmetic decoding for both binary images and multi-valued images flexibly and at the same time at a rate almost close to the limit rate determined by an arithmetic coding algorithm.
Moreover, since the present invention performs coding or decoding using a common context without distinguishing between bi-level images and multi-valued images and can thereby extremely simplify the configurations of the coder or decoder, too.
(3) Furthermore, the present invention temporarily stores arithmetic codes in memory and always reads data of predetermined bytes from the memory, and can thereby fix the code length of one block.
This makes it possible to simplify the processing of partially reconstructing images in block units, etc.